package JZ_Offer.dataStructure.tree;

import base.TreeNode;

import java.util.ArrayList;

/**
 * 二叉树中和为某一值的路径(一)
 * <p>
 * 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * (注意: 在返回值的list中，数组长度大的数组靠前)
 * <p>
 * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
 * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
 * 2.叶子节点是指没有子节点的节点
 * 3.路径只能从父节点到子节点，不能从子节点到父节点
 * 4.总节点数目为n
 *
 * @Author piper
 * @Date 2019/12/20 3:17 下午
 */
public class JZ82_二叉树中和为某一值的路径_1 {

    public boolean hasPathSum(TreeNode root, int sum) {
        // write code here
        return false;
    }

    private static void dfs(TreeNode root, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> ret) {
        path.add(root.val);
        if (target == root.val && root.left == null && root.right == null) {
            ret.add(new ArrayList<>(path));
        }

        if (root.left != null) {
            dfs(root.left, target - root.val, path, ret);
        }
        if (root.right != null) {
            dfs(root.right, target - root.val, path, ret);
        }
        // 回溯
        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        ArrayList<Integer> path = new ArrayList<>();
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        dfs(a, 7, path, ret);
        System.out.println(ret);
    }

}
